#include <stdio.h>
#define MAX_SIZE 100000

void Merge(int a[], int low, int mid, int high)
{
    int k;
    int t[MAX_SIZE];
    for (k = low; k <= high; k++)
    {
        t[k] = a[k];
    }
    k = low;
    int i = low, j = mid + 1;
    while (i <= mid && j <= high)
    {
        if (t[i] < t[j])
        {
            a[k++] = t[i++];
        }
        else
        {
            a[k++] = t[j++];
        }
    }
    while (i <= mid)
    {
        a[k++] = t[i++];
    }
    while (j <= high)
    {
        a[k++] = t[j++];
    }
}

void mergeSort(int a[], int low, int high)
{
    if (low < high)
    {
        int mid = (low + high) >> 1;
        mergeSort(a, low, mid);
        mergeSort(a, mid + 1, high);
        Merge(a, low, mid, high);
    }
}

void print(int a[], int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d\t", a[i]);
    }
}

int main()
{

    printf("\n\n========================================================================\n\n");
    int a[10] = {6, 98, 56, 32, 1, 20, 3, 45, 14, 9};
    print(a, 10);
    printf("\n");
    mergeSort(a, 0, 9);
    print(a, 10);
    printf("\n\n========================================================================\n\n");
}